package leetcode_1701_1800;

import java.util.*;

public class LeeCode_1727 {
    public static void main(String[] args) {
        System.out.println(largestSubmatrix(new int[][]{{0, 0, 1}, {1, 1, 1}, {1, 0, 1}}));
    }
    private static int largestSubmatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int ans = 0;
        for (int i = m - 2; i >= 0; i--){
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1){
                    matrix[i][j] = matrix[i + 1][j] + 1;
                }
            }
        }
        for (int[] row : matrix) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (row[j] > 0) {
                    list.add(row[j]);
                }
            }
            list.sort(Comparator.comparingInt(o -> o));
            int size = list.size();
            for (int j = 0; j < list.size(); j++) {
                int h = list.get(j);
                ans = Math.max(ans, h * (size - j));
            }
        }
        return ans;
    }
}